#pragma once

#include <mutex>
#include <condition_variable>
#include <cstdlib>

namespace mipt_parallel {

// tags: fair mutex, broadcast, loose predicate

class ticket_mutex {
    using ticket_t = std::size_t;
public:
    ticket_mutex()
        : owner_ticket_(0)
        , next_free_ticket_(0)
    {}

    void lock() {
        std::unique_lock<std::mutex> lock(mtx_);

        const ticket_t this_thread_ticket = next_free_ticket_;
        ++next_free_ticket_;

        while (this_thread_ticket != owner_ticket_) {
            unlocked_cond_.wait(lock);
        }
    }

    void unlock() {
        std::lock_guard<std::mutex> lock(mtx_);
        owner_ticket_++;
        unlocked_cond_.notify_all();
    }

private:
    ticket_t owner_ticket_;
    ticket_t next_free_ticket_;

    std::mutex mtx_;
    std::condition_variable unlocked_cond_;
};

}

